package 分治;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-02
 */
public class 颜色排序 {
    public static void main(String[] args) {
        int[] arr = {0, 1, 0, 1, 0, 2, 0, 0, 2};
        Sorting012DutchFlag(arr, arr.length);
        CommonUtil.printArr(arr);
    }

    static void Sorting012DutchFlag(int[] arr, int n) {
        //low记录low
        int low = 0, mid = 0, high = n - 1;
        while (mid <= high) {
            switch (arr[mid]) {
                case 0:
                    CommonUtil.swap(arr, low, mid);
                    low++;
                    mid++;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    CommonUtil.swap(arr, mid, high);
                    high--;
                    break;
            }
        }
    }
}